package com.mlh.binarytree;

import java.util.ArrayList;
import java.util.List;

// 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
// 如果树中有不止一个众数，可以按 任意顺序 返回。
// 假定 BST 满足如下定义：
// 结点左子树中所含节点的值 小于等于 当前节点的值
// 结点右子树中所含节点的值 大于等于 当前节点的值
// 左子树和右子树都是二叉搜索树

// 思路一：比较暴力的解法，直接用hash表来记录重复次数，这样就忽略了二叉排序树的数据结构
// 思路二：二叉排序树 中序遍历是升序，因此相同的数会集中在一起，利用这个性质来解题
public class FindMode {
	int maxCount=0;//重复最大次数
	int count,number;//count记录某个数的重复次数，number记录该数所对应的值
	List<Integer>answer=new ArrayList<>();//装结果
	public int[] method1(TreeNode root) {
		recursion(root);
		int[]res=new int[answer.size()];
		for (int i = 0; i < answer.size(); i++) {
			res[i]=answer.get(i);
		}
		return res;
	}
	public void recursion(TreeNode node){
		if(node==null){
			return;
		}
		recursion(node.left);
		// 计算该数的count
		if(node.val==number){
			count++;
		}else{
			// 第一次出现，number count重新赋值
			number=node.val;
			count=1;
		}
		// 重复次数相同，加入结果集
		if(count==maxCount){
			answer.add(number);
		}
		//发现更大的重复次数，将之前的结果集清空，更新结果集，和maxCount
		if(count>maxCount){
			answer.clear();
			answer.add(number);
			maxCount=count;
		}
		recursion(node.right);
	}
}
